import java.util.ArrayList;
import java.util.List;
import java.util.HashMap;

// 比较两张卡牌的大小
int cardCompare(String card1, String card2) {
    // 比较卡牌的花色
    int suitComparison = compareSuits(card1.charAt(1), card2.charAt(1));
    if (suitComparison != 0) {
        return suitComparison; 
    } else {
        // 如果花色相同，则比较卡牌的数值
        return Integer.compare(getRank(card1.charAt(0)), getRank(card2.charAt(0)));
    }
}

// 比较两个花色的大小
private int compareSuits(char suit1, char suit2) {
    return Integer.compare(getSuitValue(suit1), getSuitValue(suit2));
}

// 获取花色的数值表示
private int getSuitValue(char suit) {
    switch (suit) {
        case 'H': return 0; 
        case 'C': return 1; 
        case 'D': return 2; 
        case 'S': return 3; 
        default: return -1;
    }
}

// 获取卡牌数值的整数值
private int getRank(char rank) {
    switch (rank) {
        case '2': return 2;
        case '3': return 3;
        case '4': return 4;
        case '5': return 5;
        case '6': return 6;
        case '7': return 7;
        case '8': return 8;
        case '9': return 9;
        case 'T': return 10;
        case 'J': return 11; 
        case 'Q': return 12; 
        case 'K': return 13; 
        case 'A': return 14; 
        default: return 0;
    }
}

// 对卡牌数组进行冒泡排序
ArrayList<String> bubbleSort(ArrayList<String> array) {
    int n = array.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (cardCompare(array.get(j), array.get(j + 1)) > 0) {
                String temp = array.get(j);
                array.set(j, array.get(j + 1));
                array.set(j + 1, temp);
            }
        }
    }
    return array;
}

// 对卡牌数组进行归并排序
ArrayList<String> mergeSort(ArrayList<String> array) {
    if (array.size() <= 1) {
        return array; 
    }
    int mid = array.size() / 2;
    ArrayList<String> left = new ArrayList<>(array.subList(0, mid));
    ArrayList<String> right = new ArrayList<>(array.subList(mid, array.size()));
    return merge(mergeSort(left), mergeSort(right));
}

// 合并两个已排序的卡牌数组
private ArrayList<String> merge(ArrayList<String> left, ArrayList<String> right) {
    ArrayList<String> result = new ArrayList<>();
    int i = 0, j = 0;  
    while (i < left.size() && j < right.size()) {
        if (cardCompare(left.get(i), right.get(j)) <= 0) {
            result.add(left.get(i));
            i++;
        } else {
            result.add(right.get(j));
            j++;
        }
    }      
    while (i < left.size()) {
        result.add(left.get(i));
        i++;
    }
    while (j < right.size()) {
        result.add(right.get(j));
        j++;
    }
    return result;
}

// 测量冒泡排序的时间消耗
long measureBubbleSort(String filename) throws IOException {
    BufferedReader reader = new BufferedReader(new FileReader(filename));
    ArrayList<String> data = new ArrayList<>();
    String line;
    while ((line = reader.readLine()) != null) {
        data.add(line.trim());
    }
    reader.close();
    long startTime = System.nanoTime();
    bubbleSort(data);
    long endTime = System.nanoTime();
    return (endTime - startTime) / 1_000_000;
}

// 测量归并排序的时间消耗
long measureMergeSort(String filename) throws IOException {
    BufferedReader reader = new BufferedReader(new FileReader(filename));
    ArrayList<String> data = new ArrayList<>();
    String line;
    while ((line = reader.readLine()) != null) {
        data.add(line.trim());
    }
    reader.close();
    long startTime = System.nanoTime();
    mergeSort(data);
    long endTime = System.nanoTime();
    return (endTime - startTime) / 1_000_000;
}

// 比较不同文件下冒泡排序和归并排序的时间消耗
void sortComparison(String[] filenames) throws IOException {
    for (String filename : filenames) {
        long bubbleTime = measureBubbleSort(filename);
        long mergeTime = measureMergeSort(filename);
        System.out.println("File: " + filename);
        System.out.println("Bubble Sort Time: " + bubbleTime + " ms");
        System.out.println("Merge Sort Time: " + mergeTime + " ms");
    }
}